LeetCode 222 、完全二叉树的节点个数

一、题目描述

给出一个完全二叉树，求出该树的节点个数。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

提示：

• 树中节点的数目范围是[0, 5 * 10^4]
• 0 <= Node.val <= 5 * 10^4
• 题目数据保证输入的树是 完全二叉树

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 全二叉树的节点个数（ LeetCode 222 ）：https://leetcode-cn.com/problems/count-complete-tree-nodes
class Solution {

    public int countNodes(TreeNode root) {

        // 边界判断
        // 递归终止条件，如果当前节点为 null，肯定节点个数为 0
        if(root == null) {
            return 0;
        }

        // 先获取当前节点的左子树的深度
        int leftDepth = getDepth(root.left);

        // 再获取当前节点的右子树的深度
        int rightDepth = getDepth(root.right);

        // 如果 左子树的深度 等于 右子树的深度
        // 由于在完全二叉树中，对于某一层的节点来说，只有填充满了这一层的左子树的节点才会填充右子树
        // 因此，这意味着左子树是满二叉树
        if (leftDepth == rightDepth) {

            // 对于一棵满二叉树来说
            //      1
            //   /     \
            //  2        3
            // 它的节点数是 2^depth - 1
            // 位移操作，记得加括号，优先级比较低，不加容易出错
            int leftNodes = (1 << leftDepth) - 1;

            // 再去递归的获取它的右子树的节点数
            int rightNodes = countNodes(root.right);

            // 最后返回结果
            // 注意，当前节点也是需要再统计一下的
            return leftNodes + rightNodes + 1;

        // 如果 左子树的深度 不等于 右子树的深度
        // 由于在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值
        // 因此，这意味着右子树是满二叉树
        // 这样，才会出现左子树的深度比右子树的深度更深
        } else {

            // 对于一棵满二叉树来说
            //      1
            //   /     \
            //  2        3
            // 它的节点数是 2^depth - 1
            // 位移操作，记得加括号，优先级比较低，不加容易出错
            int rightNodes = (1 << rightDepth) - 1;

            // 再去递归的获取它的右子树的节点数
            int leftNodes = countNodes(root.left);

            // 最后返回结果
            // 注意，当前节点也是需要再统计一下的
            return leftNodes + rightNodes + 1;
        }
    }

    // 统计树的深度
    private int getDepth(TreeNode curNode) {

        // 默认当前节点 curNode 的深度为 0
        int depth = 0;

        // 只要 curNode 节点有值，就不断的判断
        while (curNode != null) {

            // 由于当前节点 curNode 是在一棵完全二叉树中
            // 最下面一层的节点都集中在该层最左边的若干位置
            // 即只有它的下一层左子树满了，才会填充右子树
            // 因此，如果只需要判断 curNode 的左子树是否有值就行
            curNode = curNode.left;

            // 当前节点 curNode 有值，说明深度加深了一个
            depth++;
        }

        // 返回以 curNode 作为根节点的树的深度
        return depth;
    }
}